{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 画图解释图像卷积滤波的基本原理，并进一步简述常见的图像平滑滤波算法。\n",
    "#### 滤波的基本原理\n",
    "滤波即卷积。如下图所示：\n",
    "左侧是原图像，原图像中每个小格子是像素，中间是滤波器（卷积核），右侧是滤波之后的结果。\n",
    "![image1.jpg](./1-滤波.jpg)\n",
    "图像卷积：\n",
    "1. 选定一种滤波器，将滤波器与原图像重叠，对应像素点相乘再相加，得出的数值放在中间像素位置上\n",
    "2. 将滤波器按每像素一步依次滑动，算出的结果依次填入结果图片中\n",
    "\n",
    "\n",
    "#### 常见的图像平滑滤波算法\n",
    "1. 平均滤波：在一个小区域内像素值平均，\n",
    "$$g(x,y) = \\frac{1}{M}\\sum f(m,n)$$\n",
    "如4邻域: $\\frac{1}{5}\\left[ \\begin{matrix}0& 1 &0 \\\\ 1& 1 &1 \\\\ 0&1&0 \\end{matrix} \\right]$\n",
    "8邻域: $\\frac{1}{9}\\left[ \\begin{matrix}1& 1 &1 \\\\ 1& 1 &1 \\\\ 1&1&1 \\end{matrix} \\right]$  \n",
    "2. 加权平均滤波：在平均滤波的基础上改变滤波器中每个像素点的权重，如给中心像素最大权重，距离越远权重越小。如：\n",
    "$$\\frac{1}{16}\\left[ \\begin{matrix}1& 2 &1 \\\\ 2& 4 &2 \\\\ 1&2&1 \\end{matrix} \\right]$$\n",
    "高斯滤波是一种加权平均滤波，给中心像素最大权重，距离越远权重越小。如下图所示\n",
    "![image2.jpg](./1-高斯滤波.jpg)\n",
    "3. 中值滤波：滤波器中含有奇数个像素点，取窗口内像素灰度的中位值，以此代替原窗口中心的像素值\n",
    "中值滤波可以有效消除椒盐噪声。\n",
    "\n",
    "## 2. 简述边缘检测的基本原理，以及Sobel、LoG和Canny算子的原理差异。\n",
    "#### 图像边缘检测的基本原理：\n",
    "图像的边缘一般是一阶微分有极值、二阶微分过零点的地方。  \n",
    "边缘检测的原理是设置一种卷积核，计算图像中某像素点在x, y两种方向上的微分\n",
    "#### Sobel、LoG和Canny算子：\n",
    "1. Sobel算子：  \n",
    "从x, y两个方向求取边缘。x方向中间一列均为0，y方向中间一行均为0\n",
    "2. LoG算子：  \n",
    "首先对原始图像进行高斯滤波，然后进行laplace算子。  \n",
    "laplace算子即使用中间权重高、两边权重低的滤波器求取图像边缘。如4邻域： $\\left[ \\begin{matrix}0& 1 &0 \\\\ 1& -4 &1 \\\\ 0&1&0 \\end{matrix} \\right]$  \n",
    "3. Canny算子\n",
    "可以有效降低噪声点、虚检的边缘。步骤如下：  \n",
    "    1. 使用高斯函数对图像进行平滑、计算微分\n",
    "    2. 计算在4个方向上的梯度（上下左右、斜45度）\n",
    "    3. 梯度幅值非极大值抑制。将中心像素与沿梯度方向相邻两像素的差值结果进行比较，仅保留极大值点\n",
    "    4. 边缘连接：对图像使用高低阈值进行阈值化。介于高低阈值之间的，如果有相邻像素高于高阈值，则该像素也视为阈值\n",
    "\n",
    "\n",
    "\n",
    "## 3. 简述图像直方图的基本概念，及使用大津算法进行图像分割的基本原理。\n",
    "#### 直方图的基本概念：\n",
    "以灰度图像为例，灰度直方图是以灰度为横坐标，像素出现的频次（或频率）为纵坐标\n",
    "#### 大津算法进行图像分割的基本原理\n",
    "确定一种阈值，将图像分成两类，使得两类像素的类间方差g最大:\n",
    "$$g = \\omega_0\\omega_1(\\mu_0 - \\mu_1)^2  （\\omega 某类的频率，\\mu 某类的均值）$$\n",
    "遍历254种灰度（0至255 灰度，去掉两端），计算每组的类间方差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## 4. 简述Harris算子对角点的定义，进行角点检测的基本原理，并说明引入角点响应函数的意义。 \n",
    "#### 角点的定义\n",
    "在任意方向灰度积分都剧烈变化\n",
    "\n",
    "#### 角点检测基本原理\n",
    "对图像中的某个像素在x、y两个方向上求灰度积分变化，若变化较大，则为角点\n",
    "\n",
    "#### 角点相应函数\n",
    "灰度积分的变化可以从数学方法转化为一个二次型E，而二次型可以等价为为一个椭圆，变化剧烈的方向轴短，反之轴长。\n",
    "![image2.jpg](./Harris算子原理.png)\n",
    "令$\\lambda_1^{-1/2} , \\lambda_2^{-1/2}  $为椭圆的长短轴, 当$\\lambda_1 , \\lambda_2 $都比较大时，椭圆轴短，变化剧烈，为角点。  \n",
    "角点响应函数：\n",
    "$$ R = detM-k(traceM)^2,  \n",
    "其中 traceM = \\lambda_1+\\lambda_2, detM = \\lambda_1\\lambda_2\n",
    "$$   \n",
    "通过这个角点响应函数，可以判断 ：\n",
    "- 当R接近于0时，说明$ \\lambda_1+\\lambda_2$ 趋近于0，$ \\lambda_1\\lambda_2 趋近于 \\frac{1}{k^2}$，处于灰度变化平缓的位置\n",
    "- 当$R<0$时，说明$ \\lambda_1+\\lambda_2$大，$ \\lambda_1\\lambda_2 $ 小，即该位置在一个方向变化平缓，一个方向变化剧烈，判断为边缘\n",
    "- 当$R>0$时，说明$ \\lambda_1+\\lambda_2$大，即该位置在两个方向变化剧烈，判断为角点 \n",
    "\n",
    "\n",
    "## 5. 简述Hough变换的基本原理(包括参数空间变换及参数空间划分网格统计)。 \n",
    "假设二维空间内有一条直线，在直角坐标系中可以写为$y = kx+b$。 \n",
    "每一个点可以转换为极坐标系下的一条正弦曲线$\\rho = x*cos\\theta+y*sin\\theta$。  \n",
    "当多个点源于直角坐标系中的同一条直线$y = kx+b$， 在极坐标系下必相交于一点。\n",
    "![image2.jpg](./直线检测.png)\n",
    "把极坐标系空间量化为多个小格子，计量每个小格子中正弦曲线出现的次数，格子中的次数超过阈值T，则判断为这是一条直线。\n",
    "\n",
    "## 6. 简述SIFT原理(重点是尺度空间和方向直方图原理)及ORB算子原理(重点是FAST和BRIEF)\n",
    "#### SIFT原理\n",
    "1. 尺度空间：  \n",
    "为了模仿人类视觉对不同尺度的东西有同样的认知，使用高斯模糊和尺度空间生成高斯金字塔：\n",
    "    1. 对图像做不同尺度的高斯模糊\n",
    "    2. 对图像做降采样\n",
    "接下来对尺度空间做极值检测，对每组相邻两层图像做高斯差分（DoG），得到候选的SIFT特征点\n",
    "2. 进行关键点定位\n",
    "做子像素差值，消除边缘效应\n",
    "3. 关键点特征描述\n",
    "对每个关键点所在的尺度空间值L，计算其梯度的模值和方向。  \n",
    "方向直方图：  \n",
    "    - 以关键点为中心，计算半径$3*1.5\\sigma$邻域内所有点的梯度方向，\n",
    "    - 0-360度分为n个柱子子，统计每个方向范围内关键点的幅值加权值\n",
    "总之，关键点的特征描述由如下步骤：\n",
    "    1.确定计算描述子所需的图像区域\n",
    "    2. 将坐标轴旋转为关键点的方向，以确保旋转不变性\n",
    "    3. 在图像半径区域内对每个像素点求其梯度幅值和方向，然后对每个梯度幅值诚意高斯权重参数，生成方向直方图\n",
    "    4. 在窗口宽度为设定区域内计算8个方向的梯度直方图，绘制每个梯度方向的累加值，形成一个种子点；以此计算其他种子点\n",
    "    5. 描述子向量门限化以及门限化后的描述子向量规范化\n",
    "    6.描述子向量门限，一般设置门限值0.2之后截取\n",
    "    \n",
    "\n",
    "#### ORB原理\n",
    "\n",
    "ORB算法是由FAST算法改进的。  \n",
    "FAST算法：\n",
    "1. 从图像中选一点P，画一个半径为3的圆，如果圆周上连续有N个像素的灰度值比P大或小，则p为特征点。（FAST-9即为连续9个像素或大或小）\n",
    "2. 使用机器学习决策树的方法筛选最优特征点\n",
    "3. 使用非极大值抑制的算法去除邻近位置的多个特征点\n",
    "4. 建立金字塔，每层提取的特征点总和作为该图像的特征点\n",
    "\n",
    "ORB的特征描述是由BRIEF算法改进的：\n",
    "1. 在一个特征点的邻域内，选择n对像素点$p_i, q_i (i=1,2,...,n)$,\n",
    "2. 比较每个点对灰度值的大小，记为0或1\n",
    "3. 所有点对都进行比较，生成长度为n的二进制串\n",
    "\n",
    "具有旋转不变性的BRIEF（steerBRIEF）：经过$\\theta$角度的旋转，得到新的点对，比较点对大小形成二进制串\n",
    "\n",
    "rBRIEF：\n",
    "为了改善steerBRIEF的相关性不佳的特性：\n",
    "1. 设置300k个特征点测试机，在31* 31的邻域内按M种方法取点对，比较点对大小形成一个300k * M的二进制矩阵Q\n",
    "2. 对矩阵Q的每一列求取平均值，按照平均值到0.5（代表相关性最弱）的距离重新对Q的列向量排序，形成矩阵T\n",
    "3. 将T的第一列向量放在矩阵R中\n",
    "4. 取T的下一列向量和R中所有列向量计算相关性，如果相关系数小于设定的阈值，则将T中的该列向量移动到R中\n",
    "5. 按照4的方式不断操作，直到R中有256列向量\n",
    "该256列就是选取点对的256种方法\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
